// #define print(...)

class Solution {
public:
int majorityElement(vector<int>& nums) {
    int cnt = 0, candidate = -1;
    for(auto&i:nums){
        if(0 == cnt) candidate = i;
        i == candidate ? cnt++ : cnt--;
    }
    print("\ncnt=", cnt, ", ans=", candidate, "\n")
    cnt = 0;
    for(auto&i:nums)
        if(i==candidate) cnt++;
    return cnt>nums.size()/2 ? candidate : -1;
}
};